package leetcode.year2021.month10;

import java.util.*;
import java.util.stream.IntStream;

//128. 最长连续序列

/**
 * 思路： 维护一个map，取第一个元素，然后判断包含他的最长连续序列，找到之后从map中移除元素，再遍历下一个元素，遍历到map为空为止
 */
public class _28_01LongestConsecutive128 {
  public int longestConsecutive(int[] nums) {
    int ans = 0;
    Set<Integer> numsSet = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
      numsSet.add(nums[i]);
    }
    for (Integer num : numsSet){
      if (!numsSet.contains(num - 1)){
        int currMaxLength = 1;
        int currNum = num;
        while (numsSet.contains(currNum + 1)){
          currMaxLength++;
          currNum++;
        }
        ans = Math.max(ans, currMaxLength);
      }
    }
    return ans;
  }
  /**
   * 128. 最长连续序列
   * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
   *
   * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [100,4,200,1,3,2]
   * 输出：4
   * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
   * 示例 2：
   *
   * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
   * 输出：9
   *
   *
   * 提示：
   *
   * 0 <= nums.length <= 105
   * -109 <= nums[i] <= 109
   */
}
